package edu.vt.ece.util;

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

import edu.vt.ece.main.Tester;

/**
 * User: Jeremy Tate and Brian Cheng
 * Date: 12/2/11
 * Time: 9:14 PM
 */
public class ConcurrentAVLTree extends AVLTree
{

	private volatile static int threadsWaiting = 0;
	private static ThreadLocal<Boolean> incrementedWaiting = new ThreadLocal<Boolean>() {
	    @Override
	    protected Boolean initialValue() {
	        return Boolean.FALSE;
	    }
	};

	public ConcurrentAVLTree() {
		treeLock = new ReentrantLock();
	}

	public ConcurrentAVLTree(int key) {
		root = new Node(key);
		itemsAdded.add(key);
		treeLock = new ReentrantLock();
	}

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node node) {
		root = node;
	}

	private boolean mustReset(Node currNode) {
		if(currNode==null) return false; // the tree is at root. no reset
		
		if((rebalancingLeft.compareAndSet(-1, -1)) && rebalancingRoot.compareAndSet(-1, -1)) {
			return false; // the tree didn't rebalance. no reset
		}
		if(!(rebalancingRoot.compareAndSet(-1, -1)) && rebalancingRoot.compareAndSet(1, 1)) {
			return true; // the tree rebalanced the root. reset all
		}
		if(!(rebalancingLeft.compareAndSet(-1, -1)) && (currNode.getKey() < root.getKey()) && rebalancingLeft.compareAndSet(1, 1)) {
			return true; // the tree rebalanced the left side of root and currNode is on left
		}
		if(!(rebalancingLeft.compareAndSet(-1, -1)) && (currNode.getKey() > root.getKey()) && rebalancingLeft.compareAndSet(0, 0)) {
			return true; // the tree rebalance the right side of root and currNode is on right
		}
		// the tree rebalanced itself on the other side of currNode
		return false;
	}
	
	public void getTreeLock()
	{
		while(!treeLock.tryLock()) {
			if (Tester.DEBUG_MODE) System.out.println("spinning...");
			// check for whether we are spinning on rebalance
			if( !(rebalancingLeft.compareAndSet(-1, -1)) || !(rebalancingRoot.compareAndSet(-1, -1)) ) {
				if(!incrementedWaiting.get()) {
					threadsWaiting++;
					incrementedWaiting.set(true);
				}
			}
		}
	}

	public void releaseTreeLock()
	{
		if(!treeLock.isHeldByCurrentThread()) return;

		while(treeLock.isHeldByCurrentThread()) {
			treeLock.unlock();
		}
		
		if(incrementedWaiting.get()) {
			threadsWaiting--;
			incrementedWaiting.set(false);
		}
	}

	/**
	 * Adds the item into the tree. Duplicates are not allowed.
	 *
	 * @param item
	 * @return true if the item was added successfully, false if it was already
	 *         in the tree
	 */
	public boolean add(int item) {

		Node newNode = new Node(item);
		if (root == null)
		{
			//new tree, root is the first node, return immediately
			root = newNode;
			return true;
		}

		Node currNode = root; // this is the item that we are going to compare with item
		Node nextNode = currNode;

		iterate:
			while (true) {
				if(threadsWaiting==0) {
					rebalancingLeft.set(-1);
					rebalancingRoot.set(-1);
				}
				if(incrementedWaiting.get()) {
					if (Tester.DEBUG_MODE)System.out.println("decrement Waiting");
					threadsWaiting--;
					incrementedWaiting.set(false);
				}
				
				while (true)
				{
					getTreeLock();
					if(!getLocks(currNode, nextNode)) {
						releaseLocks(currNode, nextNode);
						releaseTreeLock();
						return false;
					}
					while (item < currNode.getKey()) {
						// go left
						if (currNode.getLeft() != null) {
							nextNode = currNode.getLeft();

							if(!getLocks(currNode, nextNode)) {
								if (Tester.DEBUG_MODE) System.out.println("Giving up...");
								releaseLocks(currNode, nextNode);
								releaseTreeLock();
								return false;
							}
							releaseTreeLock();
							if(mustReset(currNode)) {
								releaseLocks(currNode, nextNode);
								currNode = root;
								continue iterate;
							}
							releaseLocks(currNode, currNode.getParent());
							currNode = nextNode;
						} else {
							break;
						}
					}
					while (item > currNode.getKey()) {
						// go right
						if (currNode.getRight() != null) {
							nextNode = currNode.getRight();

							if(!getLocks(currNode, nextNode)) {
								if (Tester.DEBUG_MODE) System.out.println("Giving up...");
								releaseLocks(currNode, nextNode);
								releaseTreeLock();
								return false;
							}
							releaseTreeLock();
							if(mustReset(currNode)) {
								releaseLocks(currNode, nextNode);
								currNode = root;
								continue iterate;
							}
							releaseLocks(currNode, currNode.getParent());
							currNode = nextNode;
						} else {
							break;
						}
					}
					if ((item < currNode.getKey() && currNode.getLeft() == null) || (item > currNode.getKey() && currNode.getRight() == null))
					{
						break iterate;
					}
					if (item == currNode.getKey())
					{
						releaseLocks(currNode, nextNode);
						return false;
					}
				}
			}

		if (item == currNode.getKey()) {
			releaseLocks(currNode, nextNode);
			return false; // duplicate key
		}
		itemsAdded.add(item); //only want unique items
		// we have gone as far as we can, now we insert the item

		if (item < currNode.getKey()) {
			currNode.setLeft(newNode);
			newNode.setParent(currNode);
		} else {
			// item > test.getKey()
			currNode.setRight(newNode);
			newNode.setParent(currNode);
		}
		currNode.releaseLock();  //todo: I got an exception from this
		releaseTreeLock();
		rebalanceAndSetRoot(newNode);
		return true;
	}

	private synchronized boolean getLocks(Node currNode, Node nextNode)
	{
		//get the lock on nextNode at the same time as currNode
		if(currNode.getLock() && nextNode.getLock()) return true;
		else return false;
	}
	
	private synchronized void releaseLocks(Node a, Node b)
	{
		if (a != null && a.lock.isHeldByCurrentThread()) a.releaseLock();
		if (b != null && b.lock.isHeldByCurrentThread()) b.releaseLock();
	}

	private void rebalanceAndSetRoot(Node node) {

		// wait until all previously waiting threads are done updating
		while(threadsWaiting!=0) ; 
		rebalancingLeft.set(-1);
		rebalancingRoot.set(-1);
		
		getTreeLock(); //rebalance is the only thing that can be working on the tree else crazy things are going to happen
		while(node.getParent()!=null) {
			Node parentNode = node.getParent();

			if(Math.abs(node.getBalanceFactor()) > 1) rebalance(node);
			node = parentNode;
		}
		if(Math.abs(node.getBalanceFactor()) <= 1) ;
		else {
			rebalance(node);
		}

		//sets root to be the parent-most parent
		while (node.getParent() != null) {
			node = node.getParent();
		}
		root = node;
		
		isValidTree(root);
		releaseTreeLock(); //done with rebalance, unlock tree
	}

	/*
	 * Removes the item from the tree.
	 */
	public boolean remove(int key) {
		Node test = contains(key);
		if (test == null)
		{
			return false;
		}
		itemsAdded.add(0 - key); //the negative items indicate those that have been removed
		Node tmpNode = removeNode(test, null);

		rebalanceAndSetRoot(tmpNode);

		return true;
	}

	private Node removeNode(Node test, Node replacementNode) {

		//determine test's relationship to parent, store in isLeft
		boolean isRoot = false;
		boolean isLeft = false;
		if(test.getParent() == null) {
			isRoot = true;
		} else {
			if(test.getParent().getLeft() == test) {
				//test is parent's left
				isLeft = true;
			}
		}

		// if test is leaf node
		if(test.getLeft() == null && test.getRight() == null) {
			if(isRoot) {
				root = null;
				return root;
			}

			if(isLeft) test.getParent().setLeft(null);
			else test.getParent().setRight(null);
			Node parent = test.getParent();
			test.setParent(null);

			if(replacementNode!=null) replacementNode.setKey(test.getKey());
			return parent;
		}

		// if test has one leaf
		if(test.getLeft() == null && test.getRight() != null) {
			if(isRoot) {
				root = test.getRight();
			}
			else {
				if(isLeft) test.getParent().setLeft(test.getRight());
				else test.getParent().setRight(test.getRight());
			}
			test.getRight().setParent(test.getParent());
			Node parent = test.getParent();
			test.setParent(null);

			if(replacementNode!=null) replacementNode.setKey(test.getKey());
			return parent;
		} else if(test.getLeft() != null && test.getRight() == null) {
			if(isRoot) {
				root = test.getLeft();
			}
			else {
				if(isLeft) {
					test.getParent().setLeft(test.getLeft());
				} else {
					test.getParent().setRight(test.getLeft());
				}
			}
			test.getLeft().setParent(test.getParent());
			Node parent = test.getParent();
			test.setParent(null);

			if(replacementNode!=null) replacementNode.setKey(test.getKey());
			return parent;
		}


		// if there are two branches
		Node tmpNode = null;
		if(test.getLeft() != null) {
			tmpNode = test.getLeft();
			while(tmpNode.getRight()!=null) tmpNode = tmpNode.getRight();
		}
		else if(test.getRight() != null) {
			tmpNode = test.getRight();
			while(tmpNode.getRight()!=null) tmpNode = tmpNode.getLeft();
		}
		else System.err.println("Should never be here.");

		return removeNode(tmpNode, test);
	}

	/**
	 * Tests whether or not a node with the specified key exists in the tree
	 * If it does, the node with that value is returned, null otherwise
	 * @param key they value to search the tree for
	 * @return the node with the specified key; false otherwise
	 */
	public Node contains(int key) {

		if(root==null) return null;
		Node currNode = root; // this is the item that we are going to compare with item
		
		iterate:
			while (true) {
				
				if(threadsWaiting==0) {
					rebalancingLeft.set(-1);
					rebalancingRoot.set(-1);
				}
				if(incrementedWaiting.get()) {
					if (Tester.DEBUG_MODE)System.out.println("decrement Waiting");
					threadsWaiting--;
					incrementedWaiting.set(false);
				}
				
				while(key!=currNode.getKey()) {
					if(currNode.getLeft()==null && currNode.getRight()==null) {
						break iterate;
					}
					
					if(key < currNode.getKey()) {
						if(currNode.getLeft()!=null) currNode = currNode.getLeft();
						else return null; //item is smaller than currNode but is not in the tree
					}
					else if(key > currNode.getKey()) {
						if(currNode.getRight()!=null) currNode = currNode.getRight();
						else return null;
					}
					
					if(mustReset(currNode)) {
						currNode = root;
						continue iterate;
					}
				}
				break iterate;
			}
		
		if(key == currNode.getKey()) {
			return currNode;
		}
		return null;
	}
}
